1. Field of the Invention
The present invention relates generally to multicast data encryption.
2. Description of the Related Art
Protecting copyrights of content owners and subscription rights of providers of the content poses considerable challenges in the digital age, particularly to content that is “streamed” to users over the Internet. In contrast to more conventional content download, in streaming paradigms the data that is being transmitted can be used by the recipient before the end of the file has been received. For time-dependent content such as music or videos, streaming requires mechanisms to ensure that data is available when needed.
“Streaming” is one common application of multicasting. In multicasting, multiple users can receive the same stream roughly simultaneously. Multicasting thus combines characteristics of broadcasting and point-to-point communications, since a copy of the data is sent to all recipients.
The rights of two separate entities are implicated in content streaming. First, the content owner typically desires that the content not be copied, i.e., that the content not be copied unless explicitly authorized. This requirement remains fixed over time. Second, the provider of the service that streams the content to users wants to ensure that only authorized users receive the stream, typically pursuant to a paid-for subscription or pay-per-view service, and that unauthorized users cannot access the content absent a subscription regardless of whether they are using copyright-compliant players. The latter requirement changes over time, since subscriptions typically are time-based and usually expire after a subscription period. The present invention thus recognizes the need for multiple enforcement domains, i.e., for a subscription enforcement domain overlaid on a copyright protection domain.
The present invention further recognizes that certain broadcast encryption schemes can be used in the streaming data application described above to achieve both copyright protection and subscription enforcement. Two such schemes are summarized here.
U.S. Pat. No. 6,118,873, incorporated herein by reference, discloses a system for encrypting broadcast music, videos, and other content. As set forth therein, only authorized players, implemented either by hardware or software, can play and/or copy the content and only in accordance with rules established by the vendor of the content.
In the encryption method disclosed in the above-referenced patent, authorized players are issued software-implemented device keys from a matrix of device keys. The keys can be issued simultaneously with each other or over time, but in any event, no player is supposed to have more than one device key per column of the matrix. Although two players might share the same key from the same column, the chances that any two players share exactly the same set of keys from all the columns of the matrix are very small when keys are randomly assigned. The keys are used to decrypt content.
In the event that a player (and its keys) becomes compromised, deliberately or by mistake, it is necessary to revoke the keys of that player. Revoking a set of keys effectively renders the compromised player (and any clones thereof) inoperable to play content that is produced after the revocation.
Another broadcast encryption method is disclosed in the above-referenced parent application, in which players are grouped into (possibly overlapping) subsets, with each subset having a unique, long-lived subset key. Each player is assigned respective private information Iu. A short-lived session encryption key K is selected, and players that are not in a revoked set R are partitioned into disjoint subsets Si1, . . . Sim having associated subset keys Li1, . . . ,Lim. The session key K is encrypted with the subset keys Li1, . . . ,Lim to render m encrypted versions of the session key K. The players establish leaves in a tree such as a complete binary tree, and the subsets Si1, . . . Sim are induced by the tree.
With more specificity, in the parent application the players are initially partitioned into groups S1, . . . ,Sw, wherein “w” is an integer. A given transmission selects m such groups as a “cover” for non-revoked players, with the cover being defined by the set of revoked players. The “cover” groups establish subtrees (either complete subtrees or a difference between two subtrees) in a tree. A player's private information Iu is preferably found as information ij in a transmitted message that indicates that a player belongs to a subset Sij of one of the groups S1, . . . ,Sw. In one embodiment, the information Iu consists of a player's position in the tree and the subset keys that are associated with ancestor nodes of the player. A subset key Lij can then be obtained from or derived using the private information of the player.
In one embodiment referred to as the “complete subtree” method, respective groups correspond to all possible subtrees in the complete tree. Each player is assigned keys from all nodes that are in a direct path between a leaf representing the player and the root of the tree. In other words, each subset S1 includes all leaves in a subtree rooted at some node v1, with at least each node in the subtree being associated with a respective subset key. In this embodiment, content is provided to players in a message defining a header, and the header includes at most r*log(N/r) subset keys and encryptions, wherein r is the number of players in the revoked set R and N is the total number of players. Moreover, each player must store log N keys, and each player processes the message using at most log N operations plus a single decryption operation.
In a second embodiment referred to as the “subset difference” method, respective groups of players correspond to a universe of sets S1, . . . ,Sw that can be described as “a first subtree A minus a second subtree B that is entirely contained in A”. Each node in this tree has a set of labels, one unique to the node and others that are induced by ancestor nodes. Each player is assigned labels from all nodes hanging from nodes in a direct path between the receiver and the root (at most logN labels from each such node), but not from nodes in the direct path itself. In other words, each subset includes all leaves in a subtree rooted at some node vi that are not in the subtree rooted at some other node vj that descends from vi. One of the labels of the subset difference nodes for a particular player are provided to the player in a transmission as that player's private information. Using the labels, the player can generate the subset keys necessary for decryption.
With respect to the subset difference method of the parent application, the revoked set R defines a spanning tree. A cover tree T is initialized as the spanning tree, and then the method iteratively removes nodes from the cover tree T and adds subtrees to the cover tree T until the cover tree T has at most one node. The cover tree T is used to identify subset keys to be used in a particular transmission, with players evaluating the pseudorandom sequence generator to derive subset keys from the labels. Preferably, for processing efficiency revocations are processed in order from left to right such that only two revocations at a time must be kept in memory.
Other less preferred encryption systems have been provided. Examples of such systems include the tree-based logical key hierarchy systems disclosed in Wallner et al., Key Management for Multicast: Issues and Architectures, IETF draft wallner-key, 1997, and Wong et al., Secure Group Communication Using Key Graphs, SIGCOMM 1998. With more specificity regarding the methods of Wallner et al. and Wong et al., keys are assigned by assigning an independent label to each node in a binary tree. Unfortunately, in the referenced methods some of the labels change at every revocation, and consequently are inappropriate for certain scenarios such as the stateless player scenario and moreover would require excessive encryptions and decryptions.